package leetcode_day._2021._202103;

import general_class.TreeNode;

import java.util.*;

/**
 * @author yzh
 * @data 2021/3/28 10:13
 * 二叉搜索树迭代器
 * 树的前中后序遍历，看得是根节点啥时遍历
 * 中序遍历：左子树 -> 根节点 -> 右子树
 * 思路：
 *  ① 定义一个数组，存放中序遍历树之后的数据
 *  ② 定义一个栈来保存节点，还有一个 cur 指向当前节点
 */
public class _28_173 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(7,
                new TreeNode(3, null, null),
                new TreeNode(15, new TreeNode(9, null, null),
                        new TreeNode(20, null, null)));
        BSTIterator bstIterator = new BSTIterator(root);
        bstIterator.mot(root);
        System.out.println(bstIterator.ans);
    }
    static class BSTIterator {
        List<Integer> ans = new ArrayList<>();
        Iterator<Integer> iterator;

        public BSTIterator(TreeNode root) {
            mot(root);
            iterator = ans.iterator();
        }

        public void mot(TreeNode root) {
            if (root.left == null && root.right == null) {
                ans.add(root.val);
                return;
            }
            if (root.left != null) mot(root.left);
            ans.add(root.val);
            if (root.right != null) mot(root.right);
        }

        public int next() {
            return iterator.next();
        }

        public boolean hasNext() {
            return iterator.hasNext();
        }
    }

    static class BSTIterator1 {
        Deque<TreeNode> stack;
        TreeNode cur;

        public BSTIterator1(TreeNode root) {
            cur = root;
            stack = new LinkedList<>();
        }

        public int next() {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            int res = cur.val;
            cur = cur.right;
            return res;
        }

        public boolean hasNext() {
            return cur !=null || !stack.isEmpty();
        }
    }
}
